COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.ss Representation of LISP functions as lists.
C00009 ENDMK
C⊗;
.ss Representation of LISP functions as lists.

	The notation for LISP functions used up to now
has been chosen so that a reader can easily grasp the
meaning of a function.  It cannot be typed directly on
a computer terminal, because it distinguishes bold face,
and it is not a good notation for
programs that are to be manipulated by other programs.
For the latter purpose, it is convenient to represent LISP functions
and programs by LISP lists.  Moreover, most LISP systems use
a list notation for LISP functions as their primary form of
input.

    LISP function definitions are built up from variables and constant
S-expressions by applying functions, by conditional expressions and by
recursion.  Thus the function definition

	%3insa x ← %4if n%3 x %4then%5 NIL %4else %5A%1 . [%4a%3 x . insa %4d%3 x]%1

has the variable %3x%1 and the atom %5A%1 at the base of its
structure and applies to them the basic LISP functions, the
function %3insa%1 being defined, conditional expressions and
recursion.  Therefore, in order to write such a function as
a LISP list, we require notations for all of these.  We proceed
as follows:

	1. A variable is translated into the same letter capitalized
so that %3x%1 becomes %5X%1.

	2. An S-expression such as the atom %5A%1 above or %5(CAR X)%1 cannot
be used to represent itself, because any S-expression can occur including
those given other interpretations.  Therefore, an S-expression %3e%1
is translated into %5(QUOTE %3e%5)%1.  Thus %5A%1 becomes %5(QUOTE A)%1
and %5(CAR X)%1
becomes %5(QUOTE (CAR X))%1.  %5NIL%1 and %5T%1 occur so frequently that they
are represented by themselves instead of with %5QUOTE%1.  Thus we write
%5NIL%1 for %5NIL%1 instead of writing %5(QUOTE NIL)%1 as our translation rule
would otherwise require.  (This convention does not introduce a real
anomaly, because it amounts to considering %5NIL%1 a variable whose
value is %5NIL%1).

	3. Function names are represented by atomic symbols so that
%3insa%1 is represented by %5INSA%1.  The basic LISP functions are called
%5CAR%1, %5CDR%1, %5CONS%1, %5ATOM%1 and %5EQ%1.

	4. The application of a function to arguments is represented
by a list consisting of the function name followed by the arguments
just as we have done with arithmetic functions in previous examples.
Thus %3insa x%1 translates to %5(INSA X)%1, %4n %3x%1 translates to
%5(NULL X)%1, and %5A%1 . [%4a %3x . insa %4d%3 x%1] translates to
%5(CONS (QUOTE A) (CONS (CAR X) (INSA (CDR X))))%1.

	5. The conditional expression

%4if%3 p1 %4then%3 a1 %4else if%3 p2 %4then%3 a2 %4else%3 ... %4else%3 an%1

is represented by %5(COND (p1 a1) (p2 a2) ... (T an))%1, so that the right
side of the definition of %3insa%1 becomes

%5(COND ((NULL X) NIL) (T (CONS (QUOTE A) (CONS (CAR X) (INSA (CDR X)))))%1.

	6. λ%3x ... z.e%1 is represented by %5(LAMBDA (x ... z) e)%1.

	7. %4label%3[f,e] is represented by %5(LABEL f e)%1.

	8. The way function definitions are represented is, alas,
implementation dependent.  Many PDP-10 systems use

%5(DE <function name> <list of argument variables> <expression defining function>)%1

so that %3insa%1 is finally defined by

%5(DE INSA (X) (COND ((NULL X) NIL) (T (CONS (QUOTE A) (CONS (CAR X) (INSA (CDR X))))))%1.

	As a second example, our old friend %3alt%1 is given by

%5(DE ALT (X) (COND ((OR (NULL X) (NULL (CDR X)) X) (T (CONS (CAR X) (ALT (CDDR X))))))%1.

	As you see, this is much less readable than the publication
language we have heretofore used, but it is much more usable by a LISP
program, because it takes the form of LISP data.  In this book, we shall
continue to use the publication language, but the internal language will
come up again when we discuss programs that interpret, translate, and/or
create LISP programs.